import java.util.LinkedList;
import java.util.List;

/**
 * @author 雷明浩
 * @date 2025/7/1 16:29
 */
public class FindKth {
    public int findKth (int[] a, int n, int K) {
        // write code here
        int len = a.length;
        int targetIndex = len - K;
        int left = 0, right = len-1;
        while (true) {
            int pivot = findPartitionIndex(a, left, right);
            if (pivot == targetIndex) {
                return a[pivot];
            } else if (pivot > targetIndex) {
                right = pivot-1;
            } else {
                left = pivot +1;
            }
        }
    }

    private int findPartitionIndex(int[] a, int left, int right) {
        int i = left + 1, j = right;
        int pivot = a[left];
        while (true) {
            while (i <= j && a[i] < pivot) {
                i++;
            }
            while (i <= j && a[j] > pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, left, j);
        return j;
    }

    private void swap(int[] a, int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
    }
}